/**
 * 
 */
package com.gwcloud.leetcode.interview100;

import java.util.Arrays;

/**
 * @ClassName   : Leetcode0041 
 * @author      : ganwei 
 * @date        : 2020年5月24日
 * @Description : Leetcode0041 缺失的第一个正数
 */
public class Leetcode0041 {
	/**
	 * -排序，不满足O(N)要求
	 */
    public int firstMissingPositive(int[] nums) {
    	Arrays.sort(nums);
    	int i = 0;
    	while(i < nums.length && nums[i] < 0){
    		i++;
    	}
    	if(i == nums.length || nums[i] > 1){
    		return 1;
    	}
    	while(nums[i+1] - nums[i] > 1 && i+1 < nums.length){
    		return nums[i++]+1;
    	}
    	
    	return nums[i+1]+1;
    }
    /**
     * -O(N)思路还没想好，待解决
     */
    public int firstMissingPositive_1(int[] nums){
    	return 0;
    }
    
    /**
     * -主函数
     */
    public static void main(String[] args){
    	
    }
}
